package 单周赛.september;

import java.util.*;

/**
 * @
 * @date 2024/05/19
 */
public class 第398场单周赛 {

    public static void main(String[] args) {

        // [4,3,1,6]
        //[[0,2],[2,3]]
//        System.out.println(Arrays.toString(isArraySpecial(new int[]{4, 3, 1, 6}, new int[][]{{0, 2}, {2, 3}})));
        System.out.println(Arrays.toString(isArraySpecial(new int[]{7, 7}, new int[][]{{1, 1}})));

    }


    public boolean isArraySpecial(int[] nums) {

        for (int i = 1; i < nums.length; i++) {

            if ((nums[i] + nums[i - 1]) % 2 == 0) {
                return false;
            }
        }

        return true;
    }


    /**
     * 双指针+贪心
     * 求出索引i开头的最长特殊数组的结尾索引是多少
     */
    public static boolean[] isArraySpecial(int[] nums, int[][] queries) {
        // 索引i开头的最长特殊数组的结尾索引是多少
        int[] record = new int[nums.length];

        int left = 0, right = 1;
        while (left < nums.length) {
            while (right < nums.length && (nums[right] + nums[right - 1]) % 2 == 1) {
                right++;
            }

            while (left < right) {
                record[left] = right - 1;
                left++;
            }
            left = right;
            right++;
        }

        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int maxRight = record[queries[i][0]];
            if (queries[i][1] <= maxRight) {
                ans[i] = true;
            }
        }
        return ans;
    }

    /**
     * 统计每个位置上不同数字出现的次数，任意两个数字出现的次数相乘结果相加即是答案
     */
    public long sumDigitDifferences(int[] nums) {
        Map<Integer, int[]> maps = new HashMap<>();
        for (int num : nums) {
            Integer idx = 0;
            while (num > 0) {
                int[] record = maps.get(idx);
                if (record == null) {
                    record = new int[10];
                    maps.put(idx, record);
                }
                record[num % 10]++;
                num /= 10;
                idx++;
            }
        }

        long ans = 0;
        for (Map.Entry<Integer, int[]> entry : maps.entrySet()) {
            int[] record = entry.getValue();

            for (int i = 0; i < record.length; i++) {
                for (int j = i + 1; j < record.length; j++) {
                    ans += record[i] * record[j];
                }
            }
        }
        return ans;
    }


    /**
     * 记忆化搜索
     * 定义 dfs (cur,k,jump,isBack) ,cur 表示当前的台阶，isBack 表示上一次是否回退
     * 了 1 层台阶
     * TODO 没有记忆化
     */
    public int waysToReachStair(int k) {

        return dfs(1, k, 0, false);

    }

    private int dfs(int cur, int k, int jump, boolean isBack) {
        if (cur > k + 1) {
            return 0;
        }
        // 注意 cur == k 不能直接返回 1
        int result = (cur == k ? 1 : 0);
        if (!isBack && cur > 0) {
            result += dfs(cur - 1, k, jump, true);
        }
        result += dfs(cur + (int) Math.pow(2, jump), k, jump + 1, false);

        return result;
    }
}
